package com.dwliu.sort;

public class QuickSort {

	/**
	 * 快速排序：挖坑填数+分治
	 * http://blog.csdn.net/morewindows/article/details/6684558
	 * @param a
	 */
	public static void quickSort(int [] a){
		quicksort(a, 0 , a.length-1);
	}
	
	/**
	 * 分治手段
	 * @param a
	 * @param left
	 * @param right
	 */
	private static void quicksort(int [] a, int left, int right){
		if(left<right){
			int pos = adjustarray(a, left, right);
			quicksort(a, left, pos-1);
			quicksort(a, pos+1, right);
		}
	}
	
	/**
	 * 挖坑填数
	 * @param a
	 * @param left
	 * @param right
	 * @return
	 */
	private static int adjustarray(int []a, int left, int right){
		
		int temp = a[left];//基准值
		int p = left; //从左向右游标
		int q = right; //从右向左游标
		
		//在写快速排序时，感到了一种对称美，从来没有感觉到如此优美，动人！
		while(p<q) {
			//从右向左，找出第一个小于temp的值
			while(p<q && a[q]>temp) {
				q--;
			}
			//将上面找到的q位置的值填a[p]的坑
			if(p<q){
				a[p] = a[q];
				p++;
			}
			//从左向右，找出第一个大于temp的值
			while(p<q && a[p]<temp) {
				p++;
			}
			//将上面找到的p位置的值填a[q]的坑
			if(p<q){
				a[q] = a[p];
				q--;
			}
		}
		a[p] = temp;
		return p;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a []= {1,6,3,4,5};
		for(int t: a)
			System.out.print(t+" ");
		System.out.println();
		quickSort(a);
		for(int t: a)
			System.out.print(t+" ");
	}
}
